#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

/*
双链式树
*/

using namespace std;

#define MAXSIZE 100 
typedef char ElemType;

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

typedef BiTree ElemType2;
typedef struct 
{
    ElemType2 data[MAXSIZE];
    int top;
}SqStack;

typedef struct {
    ElemType2 data[MAXSIZE];
    int front, rear;
} SqQueue;

//*********队列 start**************
void InitQueue(SqQueue &q){
    q.rear=q.front=0;
}

// 判断空队列
bool QEmpty(SqQueue q){
    if (q.rear==q.front) return true;
    else return false;
}

// 入队
bool EnQueue(SqQueue &q, ElemType2 e){
    if ((q.rear + 1)%MAXSIZE==q.front) return false;
    q.data[q.rear] = e;
    q.rear = (q.rear + 1)%MAXSIZE;
    return true; 
}

// 出队
bool DeQueue(SqQueue &q, ElemType2 &e){
    if (q.rear==q.front) return false;
    e = q.data[q.front];
    q.front = (q.front + 1)%MAXSIZE;
    return true; 
}

// 获取队头元素
bool GetHead(SqQueue q, ElemType2 &e){
    if (q.rear==q.front) return false;
    e = q.data[q.front];
    return true; 
}

//*********队列 end**************

//**********栈 start**************
// 初始化
void InitStack(SqStack &s){
    // 栈顶指针
    s.top = -1;
}

// 判空
bool IsEmpty(SqStack s){
    if (s.top==-1) return true;
    else return false;
}

// 取栈顶
bool GetTop(SqStack s, ElemType2 &e){
    if (s.top==-1) return false;
    e = s.data[s.top];
    return true;
}

// 入栈
bool Push(SqStack &s, ElemType2 e){
    if (s.top >= MAXSIZE-1) return false;
    s.data[++s.top] = e;
    return true;
}

// 出栈
bool Pop(SqStack &s, ElemType2 &e){
    if (s.top==-1) return false;
    e = s.data[s.top--];
    return true;
}
//**********栈 end**************

// ABD#G##E##CF###
// 构建树结构
// 通过先序创建树
void CreateBiTree(BiTree *T){
    char c;
    scanf("%c",&c);
    if('#'==c) {
        *T=NULL; //如果输出的是空格，则表示创建的子树结束
    }
    else
    {
        *T=(BiTNode*)malloc(sizeof(BiTNode)); //创建根结点
        (*T)->data=c; //向根结点中输入数据
        CreateBiTree(&((*T)->lchild)); //递归地创建左子树
        CreateBiTree(&((*T)->rchild)); //递归地创建右子树
    }
}

void visit(BiTree T){
    printf("%c", T->data);
}

//*****************递归遍历 start***************************************
// 先序遍历
void PreOrder(BiTree T){
    if(T!=NULL){
        visit(T);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

// 中序遍历
void InOrder(BiTree T){
    if(T!=NULL){
        InOrder(T->lchild);
        visit(T);
        InOrder(T->rchild);
    }
}

// 后序遍历
void PostOrder(BiTree T){
    if(T!=NULL){
        PostOrder(T->lchild);
        PostOrder(T->rchild);
        visit(T);
    }
}
//******************递归遍历 end**************************************

//*******************非递归遍历 start*************************************
// 中序遍历
void InOrder2(BiTree T, SqStack S){
    InitStack(S);
    BiTree p=T;
    while (p||!IsEmpty(S))
    {
        if(p){
            Push(S, p);
            p=p->lchild;
        }
        else{
            Pop(S, p);
            visit(p);
            p=p->rchild;
        }
    }
}

// 先序遍历
void PreOrder2(BiTree T, SqStack S){
    InitStack(S);
    BiTree p=T;
    while (p||!IsEmpty(S))
    {
        if(p){
            visit(p);
            Push(S, p);
            p=p->lchild;
        }
        else{
            Pop(S, p);
            p=p->rchild;
        }
    }
}

// 后序遍历
void PostOrder2(BiTree T, SqStack S){
    InitStack(S);
    BiTree p=T;
    BiTree r = NULL;
    while (p||!IsEmpty(S))
    {
        if(p){
            Push(S, p);
            p=p->lchild;
        }
        else{
            GetTop(S, p);
            if (p->rchild&&p->rchild!=r){
                p=p->rchild;
            }else{
                Pop(S, p);
                visit(p);
                r=p;
                p=NULL;  
            }
        }
    }
}

//*******************非递归遍历 end*************************************

//*****************层级遍历 start***********************
// 自上而下，从左到右
void LevelOrder1(BiTree T, SqQueue Q){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while(!QEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->lchild!=NULL) EnQueue(Q, p->lchild);
        if(p->rchild!=NULL) EnQueue(Q, p->rchild);
    }
}

// 自上而下，从右到左
void LevelOrder2(BiTree T, SqQueue Q){
    InitQueue(Q);
    BiTree p;
    EnQueue(Q, T);
    while(!QEmpty(Q)){
        DeQueue(Q, p);
        visit(p);
        if(p->rchild!=NULL) EnQueue(Q, p->rchild);
        if(p->lchild!=NULL) EnQueue(Q, p->lchild);
    }
}
//*****************层级遍历 end***********************

int main(){
    BiTree T=NULL;  
    SqStack S;  
    SqStack S2; 
    SqQueue Q;
    CreateBiTree(&T);
    printf("\n**************create tree done***************\n");
    printf("PreOrder:");
    PreOrder(T);
    printf("\n");
    printf("InOrder:");
    InOrder(T);
    printf("\n");
    printf("PostOrder:");
    PostOrder(T);
    printf("\n");
    printf("recursive PreOrder:");
    PreOrder2(T, S);
    printf("\n");
    printf("recursive InOrder:");
    InOrder2(T, S);
    printf("\n");
    printf("recursive PostOrder:");
    PostOrder2(T, S2);
    printf("\n");
    printf("LevelOrder1:");
    LevelOrder1(T, Q);
    printf("\n");
    printf("LevelOrder2:");
    LevelOrder2(T, Q);
    printf("\n");
    system("pause");
    return 0;
}